研究笔记 | 探索小世界网络模型（Small-world Model）
1
引言
我们生活在一个充满“网络”的时代，这里的“网络”不仅是指互联网，也包括自身所处的各种社交关系网。在过去的50年里，社会学家尝试通过网络分析（network anlaysis）来描述网络中的结构特征，理解个体之间的相互作用。本文将以小世界网络（small-world）为例，简要介绍小世界现象，其经典数学模型和代码实现方法。
2
小世界现象
小世界现象，又称为六度分隔理论（Six degrees of separation），最早在1929年匈牙利作家Frigyes Karinthy的短篇小说《链条》中提到，其核心假设为：世界上任何两个互不认识的人最多需要通过6个中间人就可以建立起必然的联系。1967年，哈佛大学心理学教授Stanley Milgram在此概念下设计了一个连锁传信实验，通过将信件随机发送给内布拉斯加州的160个人，信中有一名波士顿股票经纪人的名字，并要求每个收信人将这封信寄给自己认为比较接近股票经纪人的朋友。最终，大部分信件经过5-6次传递后到达了这名股票经纪人手中，初步证明了两个素不认识的美国人平均需要5.5个中间人就可以相互认识。
图1 Milgram连锁传信实验（图片来源：引用文献[1]）
随着互联网的兴起，小世界现象在大量社交软件平台上也得到了类似反复的证明。例如：Facebook联合米兰大学Web 算法实验室在2011年以一个月内访问Facebook的7.21亿位用户为研究对象（约占全球人口10%），基于用户间所建立的690亿条友谊关系（friendship links）进行计算，发现任意两位用户之间产生社交联系的平均距离为4.74[2]；同年，有学者随机选取了Twitter平台上的1500名用户，计算得出其平均距离为3.435。
图2 利用Facebook数据对小世界现象的验证研究（图片来源：引用文献[2]）
其中，整个 Facebook 图 (fb)、美国子图 (us)、意大利子图 (it) 、瑞典子图 (se)、以及意大利和瑞典图 (itse) 的组合，用于检查组合两个区域性但距离较远的网络是否可以显着改变平均距离
从某种意义上来讲，信息网络时代使得人类社会中普遍存在的这种“弱联系”正在逐步增强，人与人之间的社交距离也在不断缩小。因此，从复杂网络和计算思维的视角，理解于社会人际关系结构中的小世界特性，对于知识传播[3]、行为传递[4]、病毒传染[5]等相关领域研究都具有重要的价值。
3
经典数学模型
在介绍数学模型前，首先需要引入两个重要的数学概念，即平均路径长度（average path length，APL）、聚类系数（clustering coefficient，CC）。小世界网络（small-world network）中呈现大部分节点（node）都不与许多节点直接相连，但通过网络中的其他节点保持了网络整体的连通，是一种介于规则网络（regular networks）和随机网络（random networks）之间的过渡网络（图3），具有类似随机网络的短平均路径长度和规则网络的高聚类系数两个典型特征。其中，节点的路径长度是指两个节点之间的距离为连接其最短路径上所包含的边的数目，而该网络的平均路径长度是指网络中所有节点对的平均距离，该指标描述了节点彼此之间的分离程度，反映了网络的全局特征。节点的聚类系数是指与该节点相邻的所有节点之间连边的数目（k）占这些相邻节点之间最大可能连边数目（k(k-1)/2）的比例，而网络的聚集系数则是指网络中所有节点聚类系数的平均值，该指标描述了网络中节点的聚集程度，反映了网络的局部特征。
图3 小世界网络与规则、随机网络的关系（图片来源：引用文献[6]）
最经典的小世界网络模型是1998年由康奈尔大学的博士生Watts D.J.和他的导师Strogatz S.H.提出的（简称WS 小世界模型，WS small-world model）[6]，相关论文发表于《Nature》期刊上，至今已有高达5.5万次的引用量。该模型引入“随机性”概念，主要的构建规则可概括为“断边重连（rewiring）”的过程，即首先所有节点排成一圈，每个节点连向预设数量的邻点，连接方式是按照圆周上空间距离的远近逐个展开；然后把一小部分连线的终点，随机移动到其他节点上，在基本保持网络聚集性的同时，从而使其平均路径长度变短。经研究验证，这里的小部分重连概率p约为1-10%。
图5 平均路径长度、聚类系数随重连概率p的变化
其中L(0), C(0)分别为规则网络的平均路径长度和聚类系数，L(p), C(p)分别对应重连概率为p时的平均路径长度和聚类系数，L, C是以初始规则网络为标准对所有数据统一进行归一化处理。
（图片来源：引用文献[6]）
由于WS小世界模型中“断边重连”的随机化过程可能破坏网络的连通性。因此，Newman和Watts随后提出了另一种更为简单地实现小世界网络的建模思路——“随机加边”（简称为NW小世界模型，NW small-world model），即只在已有局部连线的网络图中以一定概率增加随机连线，而不删除原有的局部连线。这种模型能够保留原有连线所带来的聚集性，因而其最小聚类系数总是要比其他模型高。此外，小世界模型主要的局限性是在网络的拓扑上会产生不符合实际的度分布，也就是所有的节点都有相同的度（degree）。相较而言，用于描述现实中非齐次的无标度网络（scale-free networks）的幂律分布（power law），则可参考一种新的增长性网络模型，即优先连接模型（preferential attachment model），该模型强调了真实网络节点之间连边的概率经常有“重尾分布（heavy-tailed）”的特征，而不是由随机网络推导出的泊松分布（poisson distribution），可参考1999年Barabási 和Albert发表于《Science》的相关论文[7]，这里便不再做更多的介绍。
图5 (a)(b)为无标度网络及其度分布曲线；(c)(d)为随机网络及其度分布曲线
图片来源：https://zhuanlan.zhihu.com/p/138216968?ivk_sa=1024320u
4
代码实现方法
本小节将利用netlogo平台[8]来实现简单的WS小世界网络建模（图6），主要分为创建节点和边、设置圆形排列、断边重连三个部分，具体实现部分代码如下：
set infinity 99999 ; this is an arbitrary choice for a large number set number-rewired 0 ; initial count of rewired edges
; make the nodes and arrange them in a circle in order by who number set-default-shape turtles "circle" create-turtles num-nodes [ set color gray + 2 ] layout-circle (sort turtles) max-pxcor - 1
to rewire-one; make sure num-turtles is setup correctly else run setup first if count turtles != num-nodes [ setup ]
let potential-edges links with [ not rewired? ] ifelse any? potential-edges [ ask one-of potential-edges [ rewire-me ]end
to rewire-me let node-A end1; as long as A is not connected to everybody if [ count link-neighbors ] of end1 < (count turtles - 1) [; find a node distinct from A and not already a neighbor of "A" let node-B one-of turtles with [ (self != node-A) and (not link-neighbor? node-A) ]; wire the new edge ask node-A [ create-link-with node-B [ set color cyan set rewired? true ] ]
set number-rewired number-rewired + 1 die ; remove the old edge ]end
图6 WS小世界模型在netlogo中的演示界面
5
结语
自然和社会中存在着大量的复杂系统都可以通过“网络”加以描述，如神经网络、电力网络、交通网络、社交网络等。因此，复杂网络研究也具有多学科交叉的特点，常用的分析工具涉及了图论、组合数学、矩阵理论、概率论、遗传算法等。遗憾的是，学术界目前还未能给出对复杂网络的明确定义，如何建立一种简单方法，来实现完全符合真实统计特征的网络建模仍然有待探索。
在网络大数据爆炸式增长的今天，“天涯若比邻”的小世界现象已经到处可见，或是工作旅途上的偶遇，或是朋友圈上的点赞，不经意间发现“他认识你的朋友，而你认识他朋友的朋友”，然后感叹着一句“这世界真的好小哦！”
注：本文为非专业人士撰写，如有谬误，欢迎读者批评指正。
部分分析内容参考：https://zhuanlan.zhihu.com/p/141042297https://zhuanlan.zhihu.com/p/35705787参考文献
[1] Milgram S. The small-world problem[J]. Psychology Today, 1967, 1: 61–67.
[2] Backstrom L, Boldi P, Rosa M, et al. Four Degrees of Separation[J]. ACM, 2012, 1: 33–42.
[3] 巴志超, 李纲, 朱世伟. 科研合作网络的知识扩散机理研究[J]. 中国图书馆学报, 2016, 42(5): 68-84．
[4] 石娟, 郑鹏, 徐凌峰,等. 小世界网络中的大学生危机行为传播仿真研究[J]. 中国安全科学学报, 2019, 29(12): 21-27.
[5]李婵婵, 蒋国平, 宋玉蓉. 动态小世界社团网络上的病毒传播研究[J]. 复杂系统与复杂性科学, 2014, 11(3): 33-39.
[6] Watts DJ, Strogatz SH. Collective Dynamics of ‘Small-World’ Networks[J]. Nature,1998, 393: 440-442.
[7] Barabási AL, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286:509–512.
[8] Wilensky, U. NetLogo. Center for Connected Learning and Computer-Based Modeling, Northwestern University, 1999. Available onine at: http://ccl.northwestern.edu/netlogo/.
编辑 / 张舒
执行 / 宋一鸣
校对 / 宋一鸣
相关链接
。
相关链接